package top.minuy.structure.tree.unifind;

/**
 * 优化find函数，使用路径压缩减少树的高度
 * @author Minuy
 * @time 18:42
 * @date 2021/10/31
 */
public class UnionFindV5 implements UF {

    // 所有元素所属的位置
    int[] parent;
    // 记录各棵树的层数
    int[] rank;

    public UnionFindV5(int size) {
        parent = new int[size];
        rank = new int[size];

        for (int i = 0; i < parent.length; i++) {
            // 让元素自己指向自己
            parent[i] = i;
            // 默认一棵树只有一个元素，一层
            rank[i] = 1;
        }
    }

    /**
     * 获取并查集大小
     *
     * @return 并查集当前大小
     */
    @Override
    public int getSize() {
        return parent.length;
    }

    int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("Find failed, Index is illegal.");
        }
        // 时间复杂度为O(h)，h为p节点所在的高度
        while (parent[p] != p) {// 如果不是自己指向自己（根节点）
            parent[p] = parent[parent[p]]; // 路径压缩，让其指向父亲的父亲
            p = parent[p]; // 找到其父节点

            /*
             * 这里不需要维护rank，rank不代表准确的深度，只是说代表这棵树相对来说的排名
             * 因为在查询两棵树的时候，都对其进行了相应的优化，所以最终结果不影响合并的方向
             */
        }
        return p;
    }

    /**
     * 判断p和q是否连接
     *
     * @param p 元素1
     * @param q 元素2
     * @return 连接或者不连接
     */
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    /**
     * 将p和q所属的集合相连接
     * 时间复杂度为O(h)，h为树的高度
     *
     * @param p 元素1
     * @param q 元素2
     */
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot) {
            return;
        }

        // 不在同一棵树才合并
        // 根据两棵树的层数判断合并的方向
        // 层数少的树合并到层数大的树上
        if (rank[qRoot] > rank[pRoot]) { // q所在的树的层数大于p所在的树
            parent[pRoot] = qRoot; // p合并到q（浅的合并到大的）
            // 这里不需要维护rank，层数小的合并到层数大的上之后层数并没有变化
        } else if (rank[qRoot] < rank[pRoot]) {
            parent[qRoot] = pRoot; // q合并到p（浅的合并到大的）
        } else { // sz[qRoot] == sz[pRoot]
            parent[qRoot] = pRoot; // 随便哪棵树合并到哪棵树上都可以
            rank[pRoot] += 1; // 最终的父节点所在的树的深度加一，两棵相同的树，多了一个根节点
        }
    }
}
